import java.util.Scanner;
public class FakeCoin {
        static final int MAXNUM = 30;
        private static int FalseCoin(int[] coin, int low, int high) {
            int sum1 = 0, sum2 = 0, sum3 = 0;
            int re = 0;
            if ( low+1 == high ) {
                if ( coin[low] < coin[high] ) {
                    re = low+1;
                    return re;
                }
                else {
                    re = high+1;
                    return re;
                }
            }

            if ( (high-low+1)%2 == 0 ) {//如果n是偶数
                //前半段
                for ( int i = low; i <= low+(high-low)/2; i++ ) {
                    sum1 = sum1 + coin[i];
                }
                //后半段
                for ( int i = low+(high-low)/2+1; i <= high; i++ ) {
                    sum2 = sum2 + coin[i];
                }
                if ( sum1 > sum2 ) {
                    re = FalseCoin(coin, low+(high-low)/2+1, high);
                    return re;
                }
                else if ( sum2 > sum1 ){//sum2 > sum1
                    re = FalseCoin(coin, low, low+(high-low)/2);
                    return re;
                }
                else {

                }
            }
            else {//如果是奇数
                //前半段，除去中间的一个硬币
                for ( int i = low; i <= low+(high-low)/2-1; i++ ) {
                    sum1 = sum1 + coin[i];
                }
                //后半段，除去中间的一个硬币
                for ( int i = low+(high-low)/2+1; i <= high;i++ ) {
                    sum2 = sum2 + coin[i];
                }
                sum3 = coin[low+(high-low)/2];
                if ( sum1 > sum2 ) {
                    re = FalseCoin(coin, low+(high-low)/2+1, high);
                    return re;
                }
                else if ( sum2 > sum1 ){
                    re = FalseCoin(coin, low, low+(high-low)/2-1);
                    return re;
                }
                else {

                }
                if ( sum1+sum3 == sum2+sum3 ) {
                    re = low+(high-low)/2+1;
                    return re;
                }
            }
            return re;
        }
        public static void main(String[] args) {
            int[] coin = new int[MAXNUM];
            System.out.println("分治算法求假币问题: ");
            System.out.println("请输入硬币总的个数: ");
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            System.out.println("请输入所有硬币权值: ");
            for ( int i = 0; i < n; i++ ) {
                coin[i] = in.nextInt();
            }
            int position = FalseCoin(coin, 0, n-1);
            System.out.println("假币在 " + position + "个位置 ");
        }
    }
